Ethical and Social Issues Around Data Collection

数据收集中的伦理与社会问题

Before diving into data structures, consider the ethical implications of collecting and storing data. Every program that handles personal information must prioritize user privacy.

在深入数据结构之前，先思考收集和存储数据所带来的伦理影响。任何处理个人信息的程序都必须把用户隐私放在首位。

Introduction to Using Data Sets

使用数据集入门

A data set is a collection of specific pieces of information or data. Data sets can be manipulated and analyzed to solve a problem or answer a question.

数据集是一组具体的信息或数据。我们可以对数据集进行操作和分析，以解决问题或回答某个问题。

Array Creation and Access

数组的创建与访问

An array stores multiple values of the same type. The values can be either primitive values or object references. An array's length is established at creation and cannot be changed.

数组（array）存储多个相同类型的值。这些值既可以是基本类型的值，也可以是对象引用。数组的长度（length）在创建时就确定，之后不能改变。

Creating Arrays

创建数组

// Method 1: Using the new keyword// 方法 1：使用 new 关键字
int[] numbers = new int[5];          // {0, 0, 0, 0, 0}
double[] grades = new double[3];     // {0.0, 0.0, 0.0}
boolean[] flags = new boolean[4];   // {false, false, false, false}
String[] names = new String[3];     // {null, null, null}

// Method 2: Using an initializer list// 方法 2：使用初始化列表
int[] primes = {2, 3, 5, 7, 11};
String[] days = {"Mon", "Tue", "Wed"};

Accessing & Modifying Elements

访问与修改元素

int[] arr = {10, 20, 30, 40, 50};

// Access using index (0-based)// 使用索引访问（从 0 开始）
int first = arr[0];     // 10
int last = arr[4];      // 50

// Modify an element// 修改一个元素
arr[2] = 99;             // arr is now {10, 20, 99, 40, 50}// arr 现在是 {10, 20, 99, 40, 50}

// Array length (attribute, not method!)// 数组长度（是字段，不是方法！）
int len = arr.length;   // 5

Array Traversals

数组遍历

Traversing an array means using repetition statements to access all or an ordered sequence of elements.

遍历（traverse）数组是指用循环语句访问数组的所有元素或一段有序的元素。

Indexed for Loop

带索引的 for 循环

int[] arr = {3, 7, 1, 9, 5};
for (int i = 0; i < arr.length; i++) {
    System.out.print(arr[i] + " ");
}
// Output: 3 7 1 9 5// 输出：3 7 1 9 5

Enhanced for Loop (for-each)

增强 for 循环（enhanced for loop / for-each）

for (int val : arr) {
    System.out.print(val + " ");
}
// Output: 3 7 1 9 5// 输出：3 7 1 9 5

int[] arr = {1, 2, 3};

// Doesn't work, val is a copy// 不起作用，val 是副本
for (int val : arr) {
    val *= 2;
}
// arr is still {1, 2, 3}// arr 仍是 {1, 2, 3}

// Works, indexed for assigns through the array reference// 有效，带索引的 for 通过数组引用赋值
for (int i = 0; i < arr.length; i++) {
    arr[i] *= 2;
}
// arr is now {2, 4, 6}// arr 现在是 {2, 4, 6}

int[] arr = {1, 2, 3};

// Doesn't work, val is a copy// 不起作用，val 是副本
for (int val : arr) {
    val *= 2;
}
// arr is still {1, 2, 3}// arr 仍是 {1, 2, 3}

// Works, indexed for assigns through the array reference// 有效，带索引的 for 通过数组引用赋值
for (int i = 0; i < arr.length; i++) {
    arr[i] *= 2;
}
// arr is now {2, 4, 6}// arr 现在是 {2, 4, 6}

Implementing Array Algorithms

实现数组算法

Standard algorithms that traverse arrays to accomplish common tasks are fundamental to AP CSA.

通过遍历数组完成常见任务的标准算法，是 AP CSA 的基础内容。

findMax and average below assume a nonempty array: findMax reads arr[0], and average divides by arr.length.

下面的 findMax 和 average 假定数组非空：findMax 会读取 arr[0]，而 average 会除以 arr.length。

public static int findMax(int[] arr) {
    int max = arr[0];
    for (int val : arr) {
        if (val > max) max = val;
    }
    return max;
}

public static double average(int[] arr) {
    int sum = 0;
    for (int val : arr) {
        sum += val;
    }
    return (double) sum / arr.length;
}

// Count elements greater than a threshold// 统计大于阈值的元素
public static int countAbove(int[] arr, int threshold) {
    int count = 0;
    for (int val : arr) {
        if (val > threshold) count++;
    }
    return count;
}

// Check if ALL elements are positive// 判断是否所有元素都为正
public static boolean allPositive(int[] arr) {
    for (int val : arr) {
        if (val <= 0) return false;
    }
    return true;
}

// Check if ANY element is negative// 判断是否存在负数元素
public static boolean hasNegative(int[] arr) {
    for (int val : arr) {
        if (val < 0) return true;
    }
    return false;
}

// Shift left: {2, 4, 6, 8} becomes {4, 6, 8, 0}// 左移：{2, 4, 6, 8} 变为 {4, 6, 8, 0}
public static void shiftLeft(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++)
        arr[i] = arr[i + 1];
    arr[arr.length - 1] = 0;
}

// Shift right: {2, 4, 6, 8} becomes {0, 2, 4, 6}// 右移：{2, 4, 6, 8} 变为 {0, 2, 4, 6}
public static void shiftRight(int[] arr) {
    for (int i = arr.length - 1; i > 0; i--)
        arr[i] = arr[i - 1];
    arr[0] = 0;
}

// Rotate left: {2, 4, 6, 8} becomes {4, 6, 8, 2}// 左循环移位：{2, 4, 6, 8} 变为 {4, 6, 8, 2}
public static void rotateLeft(int[] arr) {
    int first = arr[0];
    for (int i = 0; i < arr.length - 1; i++)
        arr[i] = arr[i + 1];
    arr[arr.length - 1] = first;
}

// Rotate right: {2, 4, 6, 8} becomes {8, 2, 4, 6}// 右循环移位：{2, 4, 6, 8} 变为 {8, 2, 4, 6}
public static void rotateRight(int[] arr) {
    int last = arr[arr.length - 1];
    for (int i = arr.length - 1; i > 0; i--)
        arr[i] = arr[i - 1];
    arr[0] = last;
}

// Reverse in place: swap matching positions from the two ends// 原地反转：交换从两端向中间对应的位置
public static void reverse(int[] arr) {
    for (int i = 0; i < arr.length / 2; i++) {
        int temp = arr[i];
        arr[i] = arr[arr.length - 1 - i];
        arr[arr.length - 1 - i] = temp;
    }
}

// Check for duplicates// 检测重复元素
public static boolean hasDuplicates(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[i] == arr[j]) return true;
        }
    }
    return false;
}

// Access consecutive pairs// 访问相邻元素对
for (int i = 0; i < arr.length - 1; i++) {
    System.out.println(arr[i] + " and " + arr[i + 1]);
}

Using Text Files

使用文本文件

A file provides persistent storage, data survives after the program ends. Java uses the File and Scanner classes to read from text files.

文件提供持久化存储，数据在程序结束后依然保留。Java 使用 File 和 Scanner 类来读取文本文件。

Reading from a File

从文件读取内容

import java.io.File;
import java.io.IOException;
import java.util.Scanner;

public static int countTokens() throws IOException {
    File file = new File("data.txt");
    Scanner input = new Scanner(file);
    int count = 0;

    while (input.hasNext()) {
        String token = input.next();
        count++;
    }
    input.close();
    return count;
}

This assessed pattern uses hasNext() to test whether another item exists, next() to consume exactly one token, and close() when the file is finished. If the pathname cannot be opened, declaring throws IOException is one way to specify that the program terminates instead of continuing with missing input.

这个考试范围内的模式用 hasNext() 判断是否还有下一个项目，用 next() 恰好读取一个 token，并在文件使用完毕后调用 close()。如果路径无法打开，在方法头声明 throws IOException 是一种处理方式：程序终止，而不是在缺少输入的情况下继续运行。

The split() Method

split() 方法

String line = "Alice,90,85,92";
String[] parts = line.split(",");
// parts = {"Alice", "90", "85", "92"}// parts = {"Alice", "90", "85", "92"}

Wrapper Classes

包装类（wrapper class）

The Integer and Double classes wrap primitive types into objects. Both are immutable, once created, their values cannot change.

Integer 和 Double 类把基本类型包装成对象。它们都是不可变的——一旦创建，值就不能再改变。

Autoboxing & Unboxing

自动装箱（autoboxing）与拆箱（unboxing）

// Autoboxing: primitive → wrapper object// 自动装箱：基本类型 → 包装对象
Integer x = 5;          // int → Integer// int → Integer
Double y = 3.14;        // double → Double// double → Double

// Unboxing: wrapper object → primitive// 拆箱：包装对象 → 基本类型
int a = x;              // Integer → int// Integer → int
double b = y;           // Double → double// Double → double

The compiler also boxes and unboxes method arguments when the parameter type requires the corresponding conversion:

当方法形参需要对应类型时，编译器也会对实参自动装箱或拆箱：

public static void printInteger(Integer value) {
    System.out.println(value);
}
public static void printInt(int value) {
    System.out.println(value);
}

int primitive = 8;
Integer wrapped = 12;
printInteger(primitive);    // autoboxes int to Integer// 把 int 自动装箱为 Integer
printInt(wrapped);  // unboxes Integer to int// 把 Integer 自动拆箱为 int

Parsing Strings to Numbers

把字符串解析成数字

int num = Integer.parseInt("42");       // "42" → 42// "42" → 42
double d = Double.parseDouble("3.14"); // "3.14" → 3.14// "3.14" → 3.14

ArrayList Methods

ArrayList 的方法

An ArrayList is a mutable-size collection that stores object references. Unlike arrays, it can grow and shrink dynamically.

ArrayList 是一种大小可变的集合，用来存储对象引用。与数组不同，它可以动态地增大或缩小。

Creating an ArrayList

创建 ArrayList

import java.util.ArrayList;

ArrayList<String> names = new ArrayList<String>();
ArrayList<Integer> nums = new ArrayList<Integer>();

ArrayList<String> list = new ArrayList<String>();
list.add("A");          // ["A"]
list.add("B");          // ["A", "B"]
list.add(1, "X");      // ["A", "X", "B"]
list.set(0, "Z");      // ["Z", "X", "B"]
list.remove(1);        // ["Z", "B"]
String s = list.get(0); // "Z"
int sz = list.size();   // 2

ArrayList Traversals

ArrayList 遍历

Traversing an ArrayList works similarly to arrays but with critical pitfalls when modifying the list during traversal.

遍历 ArrayList 的方式与遍历数组类似，但在遍历过程中修改列表时存在严重的坑。

// Indexed for loop// 带索引的 for 循环
for (int i = 0; i < list.size(); i++) {
    System.out.println(list.get(i));
}

// Enhanced for loop// 增强 for 循环
for (String s : list) {
    System.out.println(s);
}

Safe Removal During Traversal

遍历过程中的安全删除

// Method 1: Traverse backward// 方法 1：倒序遍历
for (int i = list.size() - 1; i >= 0; i--) {
    if (list.get(i).equals("remove me")) {
        list.remove(i);
    }
}

// Method 2: Decrement index after removal// 方法 2：删除后将索引减一
for (int i = 0; i < list.size(); i++) {
    if (list.get(i).equals("remove me")) {
        list.remove(i);
        i--;  // adjust to not skip next element// 调整以免跳过下一个元素
    }
}

Implementing ArrayList Algorithms

实现 ArrayList 算法

The same standard algorithms from arrays apply to ArrayLists, plus the ability to insert and delete elements. Some algorithms require traversing multiple String, array, or ArrayList objects simultaneously.

数组上的那套标准算法同样适用于 ArrayList，并且还可以插入和删除元素。有些算法需要同时遍历多个 String、数组或 ArrayList 对象。

public static int findMax(ArrayList<Integer> nums) {
    int max = nums.get(0);
    for (int i = 1; i < nums.size(); i++)
        if (nums.get(i) > max) max = nums.get(i);
    return max;
}

public static double average(ArrayList<Integer> nums) {
    int sum = 0;
    for (int value : nums) sum += value;
    return (double) sum / nums.size();
}

public static boolean hasNegative(ArrayList<Integer> nums) {
    for (int value : nums)
        if (value < 0) return true;   // at least one// 至少一个
    return false;
}

public static boolean allPositive(ArrayList<Integer> nums) {
    for (int value : nums)
        if (value <= 0) return false;  // one counterexample// 一个反例即可
    return true;
}

public static int countEven(ArrayList<Integer> nums) {
    int count = 0;
    for (int value : nums)
        if (value % 2 == 0) count++;
    return count;
}

public static boolean hasAdjacentRepeat(ArrayList<String> words) {
    for (int i = 0; i < words.size() - 1; i++)
        if (words.get(i).equals(words.get(i + 1)))
            return true;
    return false;
}

public static boolean hasDuplicate(ArrayList<String> words) {
    for (int i = 0; i < words.size(); i++)
        for (int j = i + 1; j < words.size(); j++)
            if (words.get(i).equals(words.get(j)))
                return true;
    return false;
}

// Shift left, filling the final position with 0// 左移，并用 0 填充最后一个位置
public static void shiftLeft(ArrayList<Integer> nums) {
    for (int i = 0; i < nums.size() - 1; i++)
        nums.set(i, nums.get(i + 1));
    nums.set(nums.size() - 1, 0);
}

// Rotate right: save the last value before shifting right// 右循环移位：向右移动前先保存最后一个值
public static void rotateRight(ArrayList<Integer> nums) {
    int last = nums.get(nums.size() - 1);
    for (int i = nums.size() - 1; i > 0; i--)
        nums.set(i, nums.get(i - 1));
    nums.set(0, last);
}

public static void reverse(ArrayList<Integer> nums) {
    for (int i = 0; i < nums.size() / 2; i++) {
        int opposite = nums.size() - 1 - i;
        int temp = nums.get(i);
        nums.set(i, nums.get(opposite));
        nums.set(opposite, temp);
    }
}

// Remove all even numbers (traverse backward)// 删除所有偶数（倒序遍历）
for (int i = nums.size() - 1; i >= 0; i--) {
    if (nums.get(i) % 2 == 0) {
        nums.remove(i);
    }
}

// Insert separator between consecutive duplicates// 在相邻重复元素之间插入分隔符
for (int i = 0; i < list.size() - 1; i++) {
    if (list.get(i).equals(list.get(i + 1))) {
        list.add(i + 1, "---");
        i++;  // skip the inserted element// 跳过刚插入的元素
    }
}

public static int countMatches(ArrayList<String> a,
                               ArrayList<String> b) {
    int count = 0;
    for (int i = 0; i < a.size(); i++)
        if (a.get(i).equals(b.get(i))) count++;
    return count;
}

public static int countMatches(ArrayList<String> a,
                               ArrayList<String> b) {
    int count = 0;
    for (int i = 0; i < a.size(); i++)
        if (a.get(i).equals(b.get(i))) count++;
    return count;
}

2D Array Creation and Access

二维数组的创建与访问

A 2D array is stored as an array of arrays, essentially a table with rows and columns. Its size is fixed at creation.

二维数组本质上是数组的数组，相当于一张带行列的表格。它的大小在创建时就已固定。

Creating 2D Arrays

创建二维数组

// Using new (3 rows, 4 columns, all zeros)// 使用 new（3 行 4 列，全为 0）
int[][] grid = new int[3][4];

// Using initializer list// 使用初始化列表
int[][] matrix = {
    {1, 2, 3},
    {4, 5, 6}
};  // 2 rows, 3 columns// 2 行 3 列

Accessing Elements

访问元素

int val = matrix[1][2];   // row 1, col 2 → 6// 第 1 行第 2 列 → 6
matrix[0][0] = 99;       // set top-left to 99// 将左上角设为 99

// Dimensions// 维度
int rows = matrix.length;       // 2
int cols = matrix[0].length;   // 3

// Access a single row (it's a 1D array)// 访问单独一行（它本身就是一维数组）
int[] firstRow = matrix[0];     // {99, 2, 3}

2D Array Traversals

二维数组的遍历

2D arrays require nested loops to traverse all elements. Two common orderings are row-major and column-major.

二维数组需要用嵌套循环才能遍历所有元素。常见的两种遍历顺序是行优先（row-major）和列优先（column-major）。

Row-Major Order

行优先顺序

for (int r = 0; r < grid.length; r++) {
    for (int c = 0; c < grid[0].length; c++) {
        System.out.print(grid[r][c] + " ");
    }
    System.out.println();
}

Column-Major Order

列优先顺序

for (int c = 0; c < grid[0].length; c++) {
    for (int r = 0; r < grid.length; r++) {
        System.out.print(grid[r][c] + " ");
    }
}

Enhanced for Loop with 2D Arrays

二维数组中的增强 for 循环

for (int[] row : grid) {         // outer: each row (1D array)// 外层：每一行（一维数组）
    for (int val : row) {        // inner: each element// 内层：每一个元素
        System.out.print(val + " ");
    }
}

int[][] g = {
    {1, 2, 3},
    {4, 5, 6}
};

// Row-major prints: 1 2 3 4 5 6// 行优先输出：1 2 3 4 5 6
for (int r = 0; r < g.length; r++)
    for (int c = 0; c < g[0].length; c++)
        System.out.print(g[r][c] + " ");

// Column-major prints: 1 4 2 5 3 6// 列优先输出：1 4 2 5 3 6
for (int c = 0; c < g[0].length; c++)
    for (int r = 0; r < g.length; r++)
        System.out.print(g[r][c] + " ");

int[][] g = {
    {1, 2, 3},
    {4, 5, 6}
};

// Row-major prints: 1 2 3 4 5 6// 行优先输出：1 2 3 4 5 6
for (int r = 0; r < g.length; r++)
    for (int c = 0; c < g[0].length; c++)
        System.out.print(g[r][c] + " ");

// Column-major prints: 1 4 2 5 3 6// 列优先输出：1 4 2 5 3 6
for (int c = 0; c < g[0].length; c++)
    for (int r = 0; r < g.length; r++)
        System.out.print(g[r][c] + " ");

A Uniquely Defined Order: Serpentine

自定义顺序示例：蛇形遍历

A problem may define its own traversal order. In a serpentine traversal, rows with even indices move left to right and rows with odd indices move right to left. For the same grid, the output is 1 2 3 6 5 4.

题目也可能自行规定遍历顺序。在蛇形遍历中，索引为偶数的行从左向右，索引为奇数的行从右向左。对同一个网格，输出为 1 2 3 6 5 4。

for (int r = 0; r < g.length; r++) {
    if (r % 2 == 0) {
        for (int c = 0; c < g[0].length; c++)
            System.out.print(g[r][c] + " ");
    } else {
        for (int c = g[0].length - 1; c >= 0; c--)
            System.out.print(g[r][c] + " ");
    }
}

Implementing 2D Array Algorithms

实现二维数组算法

Standard 2D array algorithms extend 1D algorithms to work on the entire grid or specific rows, columns, or subsections.

标准的二维数组算法是把一维算法扩展到整张网格，或者扩展到特定的行、列或子区域上。

// Sum of row r// 第 r 行的和
public static int rowSum(int[][] grid, int r) {
    int sum = 0;
    for (int c = 0; c < grid[r].length; c++)
        sum += grid[r][c];
    return sum;
}

// Sum of column c// 第 c 列的和
public static int colSum(int[][] grid, int c) {
    int sum = 0;
    for (int r = 0; r < grid.length; r++)
        sum += grid[r][c];
    return sum;
}

public static int findMax2D(int[][] grid) {
    int max = grid[0][0];
    for (int[] row : grid) {
        for (int val : row) {
            if (val > max) max = val;
        }
    }
    return max;
}

public static int countNegative(int[][] grid,
                                int firstRow, int lastRow,
                                int firstCol, int lastCol) {
    int count = 0;
    for (int r = firstRow; r <= lastRow; r++)
        for (int c = firstCol; c <= lastCol; c++)
            if (grid[r][c] < 0) count++;
    return count;
}

// Check horizontal consecutive pairs throughout the grid// 检查整张网格中的水平相邻元素对
public static boolean hasHorizontalRepeat(int[][] grid) {
    for (int r = 0; r < grid.length; r++)
        for (int c = 0; c < grid[0].length - 1; c++)
            if (grid[r][c] == grid[r][c + 1]) return true;
    return false;
}

// Check for a duplicate anywhere within one designated row// 检查指定行内任意位置是否存在重复元素
public static boolean hasDuplicateInRow(int[][] grid, int row) {
    for (int c1 = 0; c1 < grid[0].length; c1++)
        for (int c2 = c1 + 1; c2 < grid[0].length; c2++)
            if (grid[row][c1] == grid[row][c2]) return true;
    return false;
}

// Rotate one row right// 把指定行向右循环移动
public static void rotateRowRight(int[][] grid, int row) {
    int last = grid[row][grid[0].length - 1];
    for (int c = grid[0].length - 1; c > 0; c--)
        grid[row][c] = grid[row][c - 1];
    grid[row][0] = last;
}

// Rotate one column down// 把指定列向下循环移动
public static void rotateColumnDown(int[][] grid, int col) {
    int last = grid[grid.length - 1][col];
    for (int r = grid.length - 1; r > 0; r--)
        grid[r][col] = grid[r - 1][col];
    grid[0][col] = last;
}

// Reverse one row in place// 原地反转指定行
public static void reverseRow(int[][] grid, int row) {
    for (int c = 0; c < grid[0].length / 2; c++) {
        int opposite = grid[0].length - 1 - c;
        int temp = grid[row][c];
        grid[row][c] = grid[row][opposite];
        grid[row][opposite] = temp;
    }
}

Searching Algorithms

查找（searching）算法

Linear Search

线性查找（linear search）

Linear search checks each element in order until the target is found or all elements have been checked. It works on sorted or unsorted arrays and ArrayList objects, and the search may begin at either end.

线性查找按顺序依次检查每一个元素，直到找到目标或检查完所有元素为止。它适用于有序或无序的数组和 ArrayList，并且可以从任意一端开始查找。

public static int linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) return i;
    }
    return -1;  // not found// 未找到
}

Search from the Other End and Search an ArrayList

从另一端查找与查找 ArrayList

public static int linearSearchFromRight(int[] arr, int target) {
    for (int i = arr.length - 1; i >= 0; i--)
        if (arr[i] == target) return i;
    return -1;
}

public static int linearSearch(ArrayList<String> list,
                               String target) {
    for (int i = 0; i < list.size(); i++)
        if (list.get(i).equals(target)) return i;
    return -1;
}

If duplicates exist, direction affects which matching index is returned: the left-to-right version returns the first match from the left; the right-to-left version returns the first match from the right.

如果存在重复值，查找方向会影响返回哪个匹配索引：从左向右的版本返回左侧遇到的第一个匹配，从右向左的版本返回右侧遇到的第一个匹配。

Linear Search on a 2D Array

在二维数组上的线性查找

public static boolean search2D(int[][] grid, int target) {
    for (int[] row : grid) {
        for (int val : row) {
            if (val == target) return true;
        }
    }
    return false;
}

Sorting Algorithms

排序（sorting）算法

Selection Sort

选择排序

Repeatedly finds the smallest element in the unsorted portion and swaps it into its correct final position.

不断地在未排序部分中找出最小的元素，并将它交换到它最终正确的位置上。

public static void selectionSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIdx]) minIdx = j;
        }
        int temp = arr[i];
        arr[i] = arr[minIdx];
        arr[minIdx] = temp;
    }
}

Insertion Sort

插入排序

Takes each element and inserts it into its correct (but not necessarily final) position in the sorted portion by shifting elements.

取出每个元素，通过移动其他元素，把它插入到已排序部分中正确的位置（但不一定是最终位置）。

public static void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

Start: [5, 2, 4, 6, 1, 3]

Selection sort, after pass 1: [1, 2, 4, 6, 5, 3]
  ↳ Position 0 holds the global minimum, FINAL position.

Insertion sort, after pass 1: [2, 5, 4, 6, 1, 3]
  ↳ The first two elements are sorted, but 5 is NOT in its final position.
    The 1 and 3 still to come will push it right.

起始: [5, 2, 4, 6, 1, 3]

选择排序，第 1 轮后: [1, 2, 4, 6, 5, 3]
  ↳ 位置 0 已放上全局最小值，处于最终位置。

插入排序，第 1 轮后: [2, 5, 4, 6, 1, 3]
  ↳ 前两个元素已经有序，但 5 还不在它的最终位置。
    后面还会出现的 1 和 3 会把它向右挤。

Recursion

递归（recursion）

A recursive method is a method that calls itself. Every recursive method needs at least one base case (stops the recursion) and at least one recursive call.

递归方法是会调用自身的方法。每个递归方法都至少需要一个基线条件（base case，用来终止递归）和至少一次递归调用（recursive case）。

The factorial example assumes n >= 0; a negative input would keep moving away from the base case.

下面的阶乘示例假定 n >= 0；负数输入会不断远离基线条件。

public static int factorial(int n) {
    if (n == 0)          // base case// 基线条件
        return 1;
    return n * factorial(n - 1);  // recursive call// 递归调用
}
// factorial(4) → 4 * 3 * 2 * 1 * 1 = 24// factorial(4) → 4 * 3 * 2 * 1 * 1 = 24

public static String mystery(int n) {
    if (n <= 0) return "";
    return mystery(n - 1) + n + " ";
}
// mystery(3) returns what?// mystery(3) 返回什么？

mystery(3)
= mystery(2) + 3 + " "
= (mystery(1) + 2 + " ") + 3 + " "
= ((mystery(0) + 1 + " ") + 2 + " ") + 3 + " "
= (("" + 1 + " ") + 2 + " ") + 3 + " "
= ("1 " + 2 + " ") + 3 + " "
= "1 2 " + 3 + " "
= "1 2 3 "

public static String mystery(int n) {
    if (n <= 0) return "";
    return mystery(n - 1) + n + " ";
}
// mystery(3) returns what?// mystery(3) 返回什么？

mystery(3)
= mystery(2) + 3 + " "
= (mystery(1) + 2 + " ") + 3 + " "
= ((mystery(0) + 1 + " ") + 2 + " ") + 3 + " "
= (("" + 1 + " ") + 2 + " ") + 3 + " "
= ("1 " + 2 + " ") + 3 + " "
= "1 2 " + 3 + " "
= "1 2 3 "

Recursive Searching and Sorting

递归查找与排序

Tracing Recursive Traversals

追踪递归遍历

Recursion can traverse String, array, and ArrayList objects. Current AP CSA asks you to determine the result of recursive code, not to write recursive methods. In each example, the index parameter records progress toward the base case.

递归可以遍历 String、数组和 ArrayList。当前 AP CSA 要求你判断递归代码的结果，而不是编写递归方法。在每个示例中，索引形参都记录着朝基线条件推进的过程。

// String traversal: everyOther("ABCDE", 0) returns "ACE"// String 遍历：everyOther("ABCDE", 0) 返回 "ACE"
public static String everyOther(String text, int index) {
    if (index >= text.length()) return "";
    return text.substring(index, index + 1)
           + everyOther(text, index + 2);
}

// Array traversal: sumFrom({3, 1, 4}, 0) returns 8// 数组遍历：sumFrom({3, 1, 4}, 0) 返回 8
public static int sumFrom(int[] nums, int index) {
    if (index == nums.length) return 0;
    return nums[index] + sumFrom(nums, index + 1);
}

// ArrayList traversal: for [-2, 5, 0, 7], countPositive(..., 0) returns 2// ArrayList 遍历：对 [-2, 5, 0, 7]，countPositive(..., 0) 返回 2
public static int countPositive(ArrayList<Integer> nums,
                                int index) {
    if (index == nums.size()) return 0;
    int current = 0;
    if (nums.get(index) > 0) current = 1;
    return current + countPositive(nums, index + 1);
}

Binary Search

二分查找（binary search）

Binary search requires data to be sorted. It starts at the middle and eliminates half of the remaining elements each step.

二分查找要求数据必须有序。它从中间开始，每一步都把剩下的元素排除掉一半。

Binary search can be implemented iteratively or recursively on a sorted array or ArrayList. The recursive array version below is for tracing; students are not required to write recursive code.

二分查找可以用迭代或递归方式处理有序数组或 ArrayList。下面的递归数组版本用于追踪；学生不需要编写递归代码。

public static int binarySearch(int[] arr, int lo, int hi, int target) {
    if (lo > hi) return -1;  // base case: not found// 基线条件：未找到
    int mid = (lo + hi) / 2;
    if (arr[mid] == target) return mid;
    else if (arr[mid] < target)
        return binarySearch(arr, mid + 1, hi, target);
    else
        return binarySearch(arr, lo, mid - 1, target);
}

Merge Sort

归并排序

Merge sort is a recursive sorting algorithm for arrays or ArrayList objects. It divides the collection in half, sorts each half, then merges the sorted halves together.

归并排序是一种用于数组或 ArrayList 对象的递归排序算法：把集合对半分开，分别对两半进行排序，然后再把已排序的两半合并起来。

// Trace: merge sort on [38, 27, 43, 3]// 追踪：对 [38, 27, 43, 3] 进行归并排序
// Split: [38, 27] and [43, 3]// 分解：[38, 27] 和 [43, 3]
// Split: [38] [27]    [43] [3]// 分解：[38] [27]    [43] [3]
// Merge: [27, 38]     [3, 43]// 合并：[27, 38]     [3, 43]
// Merge: [3, 27, 38, 43]// 合并：[3, 27, 38, 43]

Common Unit 4 MCQ Patterns

单元 4 常见选择题模式

Unit 4 carries the most weight on the AP CSA MCQ section. The questions cluster around a handful of operational pitfalls. Knowing the pattern usually beats tracing the whole snippet.

单元 4 在 AP CSA 选择题中占比最大。题目集中考查几类操作上的陷阱。摸清套路往往比从头追踪整段代码更高效。

Flashcards

闪卡

Click each card to flip and reveal the answer.

点击每张卡片翻面查看答案。

Unit 4, Practice Quiz

单元 4 · 练习小测

AP-Style Practice Problems

AP 风格练习题